#include <memory>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <ctime>
#include <random>

int random_int(const int &min, const int &max)
{
    std::default_random_engine e;
    std::uniform_int_distribution<int> u(2, 20); // 左闭右闭区间
    e.seed(time(0));
    return u(e);
}

std ::vector<int> zero_vector(int size)
{
    std::vector<int> v;
    for (int i = 0; i < size; i++)
    {
        v.push_back(0);
    }
    return v;
}
struct Solution
{
    std::vector<int> route;
    double cost = 0;
} soluion;

class Lns
{
private:
    std::vector<std::vector<double>> distance;
    int num_node;
    /* data */
public:
    Lns(/* args */);
    ~Lns();
    Lns(std::vector<std::vector<double>> distance, int num_node)
    {
        this->distance = distance;
        this->num_node = num_node;
    }
    double get_route_cost(const std::vector<int> &route)
    {
        double cost = 0;
        for (int i = 1; i < route.size(); i++)
        {
            cost += this->distance[route[i - 1]][route[i]];
        }
        return cost;
    }
    std::vector<int> destroy_operator(Solution &soluion, int num_destroy)
    {
        std::vector<int> destroy_node_bank;
        while (destroy_node_bank.size() < num_destroy)
        {
            int n = random_int(0, this->num_node - 1);
            while (std::find(destroy_node_bank.begin(), destroy_node_bank.end(), n) != destroy_node_bank.end())
            {
                n = random_int(0, this->num_node - 1);
            }
            destroy_node_bank.push_back(n);
            soluion.route.erase(std::find(destroy_node_bank.begin(), destroy_node_bank.end(), n));
        }
        return destroy_node_bank;
    }

    void repair_operator(Solution &soluion, const std::vector<int> destroy_node_bank)
    {
        for (int n : destroy_node_bank)
        {
            int len = soluion.route.size();
            std::vector<int> insert_list = zero_vector(len);
            for (int i = 0; i < len; ++i)
            {
                insert_list[i] = this->distance[soluion.route[i - 1]][n] +
                                 this->distance[n][soluion.route[i]] -
                                 this->distance[soluion.route[i]][soluion.route[i - 1]];
            }
            int greedy_index = std::min_element(insert_list.begin(), insert_list.end()) - insert_list.begin();
            soluion.route.insert(soluion.route.begin() + greedy_index, n);
        }
    }

    void print_best_values_iteration(std::vector<double> best_value_record)
    {
        for (int i = 0; i < best_value_record.size(); i++)
        {
            std::cout << "第 " << i << " 轮，最优结果为：" << best_value_record[i] << std::endl;
        }
    }

    std::vector<std::vector<int>> get_city_location(int city_size)
    {
        std::vector<std::vector<int>> city_location;
        for (int i = 0; i < city_size; i++)
        {
            std::vector<int> temp;
            for (int i = 0; i < 2; i++)
            {
                temp.push_back(random_int(0, 100));
            }
            city_location.push_back(temp);
        }
        return city_location;
    }

    std::vector<std::vector<double>> get_distance(int n)
    {
        std::vector<std::vector<double>> distance;
        for (int i = 0; i < n; i++)
        {
            std::vector<double> temp;
            for (int j = 0; j < n; j++)
            {
                /* code */
                temp.push_back(0);
            }
            distance.push_back(temp);
        }
        return distance;
    }

    std::vector<int> get_route(int n)
    {
        std::vector<int> route;
        for (int i = 0; i < n; i++)
        {
            route.push_back(i);
        }
        return route;
    }

    void slove()
    {
        std::vector<std::vector<int>> city_location = this->get_city_location(20);
        int num_node = city_location.size();
        int iter_num = 300;
        int num_destroy = (int)num_node * 0.2;
        this->distance = this->get_distance(num_node);
        for (int i = 0; i < num_node; i++)
        {
            for (int j = 0; j < num_node; j++)
            {
                this->distance[i][j] = pow(pow(city_location[i][0] - city_location[j][0], 2) + pow(city_location[i][1] - city_location[j][1], 2), 0.5);
            }
        }
        soluion.route = get_route(num_node);
        soluion.cost = get_route_cost(soluion.route);

        /*结构体的深拷贝*/
        Solution best_solution = soluion;
        std::vector<double> best_value_record;
        for (int i = 0; i < iter_num; i++)
        {
            best_value_record.push_back(0);
        }
        for (int i = 0; i < iter_num; i++)
        {
            /*深拷贝需要注意*/
            Solution temp_solution = soluion;
            auto destroy_node_bank = this->destroy_operator(temp_solution, num_destroy);
            this->repair_operator(temp_solution, destroy_node_bank);
            temp_solution.cost = this->get_route_cost(temp_solution.route);
            if (temp_solution.cost < best_solution.cost)
            {
                soluion = temp_solution;
                best_solution = temp_solution;
            }
            best_value_record[i] = best_solution.cost;
        }

        std::cout << "-------------- output result --------------" << std::endl;
        for (int i = 0; i < best_value_record.size(); i++)
        {
            std::cout << "第 " << i << " 轮，最优结果为：" << best_value_record[i] << std::endl;
        }
    }
};

Lns::Lns(/* args */)
{
}

Lns::~Lns()
{
}

int main()
{
    Lns lns;
    lns.slove();
    return 0;
}